{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximal Range That Each Element Is Maximum in It"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumLengthOfRanges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每个元素为最大值的最大范围"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现给定一个由 <strong>不同</strong> 整数构成的 <strong>0</strong> 索引数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>我们用以下方式定义与 <code>nums</code> 长度相同的 <strong>0</strong> 索引数组 <code>ans</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>ans[i]</code> 是子数组 <code>nums[l..r]</code> 的 <strong>最大</strong> 长度，该子数组中的最大元素等于 <code>nums[i]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回数组 <code>ans</code> 。</p>\n",
    "\n",
    "<p><strong>注意</strong>，<strong>子数组</strong> 是数组的连续部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,5,4,3,6]\n",
    "<b>输出：</b>[1,4,2,1,5]\n",
    "<b>解释：</b>对于 nums[0]，最长的子数组，其中最大值为 1，是 nums[0..0]，所以 ans[0] = 1。 \n",
    "对于 nums[1]，最长的子数组，是 nums[0..3]，其中最大值为 5，所以 ans[1] = 4。 \n",
    "对于 nums[2]，最长的子数组，是 nums[2..3]，其中最大值为 4，所以 ans[2] = 2。 \n",
    "对于 nums[3]，最长的子数组，是 nums[3..3]，其中最大值为 3，所以 ans[3] = 1。 \n",
    "对于 nums[4]，最长的子数组，是 nums[0..4]，其中最大值为 6，所以 ans[4] = 5。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3,4,5]\n",
    "<b>输出：</b>[1,2,3,4,5]\n",
    "<b>解释：</b>对于 nums[i]，最长的子数组，是 nums[0..i]，其中最大值与 nums[i] 相等，所以 ans[i] = i + 1。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>所有&nbsp;<code>nums</code> 中的元素都是不重复的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximal-range-that-each-element-is-maximum-in-it](https://leetcode.cn/problems/maximal-range-that-each-element-is-maximum-in-it/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximal-range-that-each-element-is-maximum-in-it](https://leetcode.cn/problems/maximal-range-that-each-element-is-maximum-in-it/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,4,3,6]', '[1,2,3,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        a = [-1]\n",
    "        n = len(nums)\n",
    "        ret = [0] * n\n",
    "        for i in range(n):\n",
    "            while len(a) > 1 and nums[a[-1]] < nums[i]:\n",
    "                ret[a[-1]] = i - 1 - a[-2]\n",
    "                del a[-1]\n",
    "            a.append(i)\n",
    "\n",
    "        while len(a) > 1:\n",
    "            ret[a[-1]] = n - 1 - a[-2]\n",
    "            del a[-1]\n",
    "        \n",
    "        #print(f'{ret = }')\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        nums = [100001] + nums + [100001]\n",
    "        n = len(nums)\n",
    "        ans = [0] * n \n",
    "        queue = [0]\n",
    "        for i in range(1,n):\n",
    "            while nums[queue[-1]] < nums[i]:\n",
    "                j = queue.pop()\n",
    "                ans[j] = i - queue[-1] - 1\n",
    "            queue.append(i)\n",
    "        \n",
    "        return ans[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        #求关于当前点左边第一个大于当前值的点以及右边第一个当前值的点\n",
    "        #所以我们维护两次单调递减栈,一次正序,一次逆序,最后相加答案,但节点本身重复一次,故最终答案需减一。。。\n",
    "        n=len(nums)\n",
    "        nums=[inf]+nums\n",
    "        stack,ans=[0],[0]*n\n",
    "        for i in range(1,n+1):\n",
    "            while nums[i]>nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            ans[i-1]=i-stack[-1]\n",
    "            stack.append(i)\n",
    "        nums=nums[1:]+[inf]\n",
    "        stack=[n]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while nums[i]>nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            ans[i]+=stack[-1]-i-1\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        #求关于当前点左边第一个大于当前值的点以及右边第一个当前值的点\n",
    "        n=len(nums)\n",
    "        nums=[inf]+nums\n",
    "        stack,ans=[0],[0]*n\n",
    "        for i in range(1,n+1):\n",
    "            while nums[i]>nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            ans[i-1]=i-stack[-1]\n",
    "            stack.append(i)\n",
    "        nums=nums[1:]+[inf]\n",
    "        stack=[n]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while nums[i]>nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            ans[i]+=stack[-1]-i-1\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        #求关于当前点左边第一个大于当前值的点以及右边第一个当前值的点\n",
    "        n=len(nums)\n",
    "        nums=[inf]+nums\n",
    "        stack,ans=[0],[0]*n\n",
    "        for i in range(1,n+1):\n",
    "            while nums[i]>nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            ans[i-1]=i-stack[-1]\n",
    "            stack.append(i)\n",
    "        nums=nums[1:]+[inf]\n",
    "        stack=[n]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while nums[i]>nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            ans[i]+=stack[-1]-i-1\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[1]*n\n",
    "        ls=[]\n",
    "        for i,k in enumerate(nums):\n",
    "            while ls and nums[ls[-1]]<k:\n",
    "                ls.pop()\n",
    "            if ls:ans[i]+=i-1-ls[-1]\n",
    "            else:ans[i]+=i\n",
    "            ls.append(i)\n",
    "        rs=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            k=nums[i]\n",
    "            while rs and nums[rs[-1]]<k:\n",
    "                rs.pop()\n",
    "            if rs:ans[i]+=rs[-1]-1-i\n",
    "            else:ans[i]+=n-1-i\n",
    "            rs.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n, stack = len(nums), []\n",
    "        result = [0] * n\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                stack.pop()\n",
    "            result[i] = ~stack[-1] if stack else 0\n",
    "            stack.append(i)\n",
    "        stack.clear()\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                stack.pop()\n",
    "            result[i] += stack[-1] if stack else n\n",
    "            stack.append(i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        def findLeftMax(nums: List[int]) -> List[int]:\n",
    "            # 里面的元素都是index\n",
    "            stack = []\n",
    "            n = len(nums)\n",
    "            # -1代表不存在左侧最大\n",
    "            ans = [-1]*n\n",
    "            for i in range(n):\n",
    "\n",
    "                while stack:\n",
    "                    if nums[stack[-1]] > nums[i]:\n",
    "                        ans[i] = stack[-1]\n",
    "                        break\n",
    "                    elif nums[stack[-1]] <= nums[i]:\n",
    "                        stack.pop()\n",
    "                stack.append(i)\n",
    "            return ans\n",
    "        # 寻找右侧最大值\n",
    "        # 是一个从底到顶的单调递增栈，栈顶元素遇到更大的出栈\n",
    "        def findRightMax(nums:List[int]) -> List[int]:\n",
    "            stack = []\n",
    "            n = len(nums)\n",
    "            ans = [n]*n\n",
    "            for i in range(n):\n",
    "                while stack:\n",
    "                    if nums[stack[-1]] < nums[i]:\n",
    "                        temp = stack.pop()\n",
    "                        ans[temp] = i\n",
    "                    elif nums[stack[-1]] >= nums[i]:\n",
    "                        break\n",
    "                stack.append(i)\n",
    "            return ans\n",
    "        ## \n",
    "        n = len(nums)\n",
    "        leftMax = findLeftMax(nums)\n",
    "        rightMax = findRightMax(nums)\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            ret.append(rightMax[i]- 1 - leftMax[i] + 1 - 1)\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "                \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(nums)        \n",
    "        stack = []\n",
    "        lefts = [-1]*n\n",
    "        rights = [n]*n\n",
    "\n",
    "        for j in range(n):\n",
    "            while stack and nums[stack[-1]]<nums[j]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                lefts[j]=stack[-1]\n",
    "            stack.append(j)\n",
    "        \n",
    "        stack.clear()\n",
    "        for j in range(n-1,-1,-1):\n",
    "            while stack and nums[stack[-1]]<nums[j]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                rights[j]=stack[-1]\n",
    "            stack.append(j)\n",
    "        \n",
    "        return [rights[j]-lefts[j]-1 for j in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        def findLeftMax(nums: List[int]) -> List[int]:\n",
    "            # 里面的元素都是index\n",
    "            stack = []\n",
    "            n = len(nums)\n",
    "            # -1代表不存在左侧最大\n",
    "            ans = [-1]*n\n",
    "            for i in range(n):\n",
    "\n",
    "                while stack:\n",
    "                    if nums[stack[-1]] > nums[i]:\n",
    "                        ans[i] = stack[-1]\n",
    "                        break\n",
    "                    elif nums[stack[-1]] <= nums[i]:\n",
    "                        stack.pop()\n",
    "                stack.append(i)\n",
    "            return ans\n",
    "        # 寻找右侧最大值\n",
    "        # 是一个从底到顶的单调递增栈，栈顶元素遇到更大的出栈\n",
    "        def findRightMax(nums:List[int]) -> List[int]:\n",
    "            stack = []\n",
    "            n = len(nums)\n",
    "            ans = [n]*n\n",
    "            for i in range(n):\n",
    "                while stack:\n",
    "                    if nums[stack[-1]] < nums[i]:\n",
    "                        temp = stack.pop()\n",
    "                        ans[temp] = i\n",
    "                    elif nums[stack[-1]] >= nums[i]:\n",
    "                        break\n",
    "                stack.append(i)\n",
    "            return ans\n",
    "        ## \n",
    "        n = len(nums)\n",
    "        leftMax = findLeftMax(nums)\n",
    "        rightMax = findRightMax(nums)\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            ret.append(rightMax[i] - 1 - (leftMax[i] + 1) + 1)\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "                \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        r_greater = [n]*n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[i]>nums[stack[-1]]:\n",
    "                r_greater[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        l_greater = [-1]*n\n",
    "        stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and nums[i]>nums[stack[-1]]:\n",
    "                l_greater[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        return [j-i-1 for i,j in zip(l_greater,r_greater)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(nums)        \n",
    "        stack = []\n",
    "        left = [-1]*n\n",
    "        right = [n]*n\n",
    "\n",
    "        for j in range(n):\n",
    "            while stack and nums[stack[-1]]<nums[j]:\n",
    "                right[stack.pop()]=j\n",
    "            if stack:\n",
    "                left[j]=stack[-1]\n",
    "            stack.append(j)\n",
    "        \n",
    "        return [right[j]-left[j]-1 for j in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and nums[st[-1]] < nums[i]:\n",
    "                right[st.pop()] = i\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        return [r - l - 1 for l, r in zip(left, right)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(nums)        \n",
    "        stack = []\n",
    "        left = [-1]*n\n",
    "        right = [n]*n\n",
    "\n",
    "        for j in range(n):\n",
    "            while stack and nums[stack[-1]]<nums[j]:\n",
    "                right[stack.pop()]=j\n",
    "            if stack:\n",
    "                left[j]=stack[-1]\n",
    "            stack.append(j)\n",
    "        \n",
    "        return [right[j]-left[j]-1 for j in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)        \n",
    "        stack = []\n",
    "        left = [-1]*n\n",
    "        right = [n]*n\n",
    "\n",
    "        for j in range(n):\n",
    "            while stack and nums[stack[-1]]<nums[j]:\n",
    "                right[stack.pop()]=j\n",
    "            if stack:\n",
    "                left[j]=stack[-1]\n",
    "            stack.append(j)\n",
    "        \n",
    "        return [right[j]-left[j]-1 for j in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stk = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while stk and nums[stk[-1]] <= x:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                left[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] <= nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                right[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        return [r - l - 1 for l, r in zip(left, right)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n \n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            while s and nums[s[-1]] < nums[i]:\n",
    "                right[s.pop()] = i \n",
    "            if s:\n",
    "                left[i] = s[-1]\n",
    "            s.append(i)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            ans.append(right[i] - left[i] - 1)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "\n",
    "        stack = []\n",
    "        for i, num in enumerate(nums):\n",
    "\n",
    "            while stack and nums[stack[-1]] <= num:\n",
    "                poped = stack.pop()\n",
    "                right[poped] = i\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            \n",
    "            stack.append(i)\n",
    "\n",
    "        return [ right[i] - left[i] - 1 for i in range(n)]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and nums[st[-1]] <= nums[i]:\n",
    "                right[st.pop()] = i\n",
    "            st.append(i)\n",
    "\n",
    "        st = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while st and nums[st[-1]] < nums[i]:\n",
    "                left[st.pop()] = i\n",
    "            st.append(i)\n",
    "\n",
    "        \n",
    "        res = [0] * n\n",
    "        for i in range(len(nums)):\n",
    "            res[i] = right[i] - left[i] - 1\n",
    " \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n, stack = len(nums), []\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] < x:\n",
    "                right[stack.pop()] = i\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        return [r - l - 1 for l, r in zip(left, right)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left = [-1 for _ in range(n)]\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and nums[st[-1]] <= nums[i]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        right = [n for _ in range(n)]\n",
    "        while st:\n",
    "            st.pop()\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            while st and nums[st[-1]] <= nums[i]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                right[i] = st[-1]\n",
    "            st.append(i)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            l,r = left[i] + 1,right[i] - 1\n",
    "            ans.append(r - l + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        stack = list()\n",
    "        right = [0]*len(nums)\n",
    "        left = [0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                x = stack.pop()\n",
    "                right[x] = max(i-1, x)\n",
    "            stack.append(i)\n",
    "        for x in stack:\n",
    "            right[x] = max(stack[-1], x)\n",
    "        \n",
    "        stack = list()\n",
    "        nums = nums[::-1]\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                x = stack.pop()\n",
    "                left[x] = max(i-1, x)\n",
    "            stack.append(i)\n",
    "        for x in stack:\n",
    "            left[x] = max(stack[-1], x)\n",
    "        \n",
    "        left = left[::-1]\n",
    "        left = [len(nums)-x-1 for x in left]\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = right[i]-left[i]+1\n",
    "        \n",
    "        return nums\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        # a[i] 左/右侧第一个 大于 a[i] 的位置\n",
    "        st = []\n",
    "        n = len(nums)\n",
    "        right = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x = nums[i]\n",
    "            while st and x >= nums[st[-1]]:\n",
    "                st.pop()\n",
    "            right[i] = st[-1] - i - 1 if st else n - 1 - i\n",
    "            st.append(i)\n",
    "        left = [0] * n\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            while st and x >= nums[st[-1]]:\n",
    "                st.pop()\n",
    "            left[i] = i - st[-1] - 1 if st else i\n",
    "            st.append(i)\n",
    "        return [l + r + 1 for l, r in zip(left, right)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        left=list(range(n))\n",
    "        right=[n]*n\n",
    "        stack=[]\n",
    "        for i,k in enumerate(nums):\n",
    "            while stack and nums[stack[-1]]<k:\n",
    "                temp=stack.pop()\n",
    "                left[i]=left[temp]\n",
    "                right[temp]=i\n",
    "            stack.append(i)\n",
    "        return [right[i]-left[i] for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        left=list(range(n))#左侧起点\n",
    "        right=[n]*n#右侧终点\n",
    "        stack=[]\n",
    "        for i,k in enumerate(nums):\n",
    "            while stack and nums[stack[-1]]<k:\n",
    "                temp=stack.pop()\n",
    "                left[i]=left[temp]\n",
    "                right[temp]=i\n",
    "            stack.append(i)\n",
    "        return [right[i]-left[i] for i in range(n)]\n",
    "        \n",
    "\n",
    "    def maximumLengthOfRanges2(self, nums: List[int]) -> List[int]:\n",
    "        has, stark = [[-1, len(nums)] for _ in range(len(nums))], []\n",
    "        for i, v in enumerate(nums):\n",
    "            while stark and nums[stark[-1]] < v: has[stark.pop()][1] = i\n",
    "            if stark: has[i][0] = stark[-1]\n",
    "            stark.append(i)\n",
    "        return [j - i - 1 for i, j in has]\n",
    "        \n",
    "\n",
    "    def maximumLengthOfRanges3(self, nums: List[int]) -> List[int]:\n",
    "        nums.append(100001) # 设置哨兵\n",
    "        n = len(nums)\n",
    "        has, stark = [[-1, -1] for _ in range(n)], [-1]\n",
    "        for i in range(n):\n",
    "            v = nums[i]\n",
    "            while nums[stark[-1]] < v: has[stark.pop()][1] = i\n",
    "            has[i][0] = stark[-1]\n",
    "            stark.append(i)\n",
    "        return [j - i - 1 for i, j in has[:-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "from typing import List, Tuple\n",
    "\n",
    "\n",
    "def getRange(\n",
    "    nums: List[int],\n",
    "    isMax=False,\n",
    "    isLeftStrict=True,\n",
    "    isRightStrict=False,\n",
    ") -> List[Tuple[int, int]]:\n",
    "    \"\"\"\n",
    "    求每个元素作为最值的影响范围(区间)\n",
    "    默认为每个数作为左严格右非严格最小值的影响区间 [left,right]\n",
    "\n",
    "    有时候为了避免重复计算，我们可以考虑左侧`严格小于`当前元素的最近元素位置，\n",
    "    以及右侧`小于等于`当前元素的最近元素位置。\n",
    "    \"\"\"\n",
    "\n",
    "    def compareLeft(stackValue: int, curValue: int) -> bool:\n",
    "        if isLeftStrict and isMax:\n",
    "            return stackValue <= curValue\n",
    "        elif isLeftStrict and not isMax:\n",
    "            return stackValue >= curValue\n",
    "        elif not isLeftStrict and isMax:\n",
    "            return stackValue < curValue\n",
    "        else:\n",
    "            return stackValue > curValue\n",
    "\n",
    "    def compareRight(stackValue: int, curValue: int) -> bool:\n",
    "        if isRightStrict and isMax:\n",
    "            return stackValue <= curValue\n",
    "        elif isRightStrict and not isMax:\n",
    "            return stackValue >= curValue\n",
    "        elif not isRightStrict and isMax:\n",
    "            return stackValue < curValue\n",
    "        else:\n",
    "            return stackValue > curValue\n",
    "\n",
    "    n = len(nums)\n",
    "    leftMost = [0] * n\n",
    "    rightMost = [n - 1] * n\n",
    "\n",
    "    stack = []\n",
    "    for i in range(n):\n",
    "        while stack and compareRight(nums[stack[-1]], nums[i]):\n",
    "            rightMost[stack.pop()] = i - 1\n",
    "        stack.append(i)\n",
    "\n",
    "    stack = []\n",
    "    for i in range(n - 1, -1, -1):\n",
    "        while stack and compareLeft(nums[stack[-1]], nums[i]):\n",
    "            leftMost[stack.pop()] = i + 1\n",
    "        stack.append(i)\n",
    "\n",
    "    return list(zip(leftMost, rightMost))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        ranges = getRange(nums, isMax=True, isLeftStrict=False, isRightStrict=False)\n",
    "        return [right - left + 1 for left, right in ranges]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        nums.append(100001)\n",
    "        n = len(nums)\n",
    "        has, stark = [[-1, -1] for _ in range(n)], [-1]\n",
    "        for i in range(n):\n",
    "            v = nums[i]\n",
    "            while nums[stark[-1]] < v: has[stark.pop()][1] = i\n",
    "            has[i][0] = stark[-1]\n",
    "            stark.append(i)\n",
    "        return [j - i - 1 for i, j in has[:-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        has = [[-1,n] for _ in range(n)]\n",
    "        stark = []\n",
    "        for i in range(n):\n",
    "            vl = nums[i]\n",
    "            while stark and nums[stark[-1]] < vl:\n",
    "                has[stark.pop()][1] = i\n",
    "            if stark:\n",
    "                has[i][0] = stark[-1]\n",
    "            stark.append(i)\n",
    "        return [has[i][1] - has[i][0] - 1 for i in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        res = [[-1, len(nums)] for _ in range(len(nums))]\n",
    "        stack = []\n",
    "        for i, n in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] < n:\n",
    "                res[stack.pop()][1] = i\n",
    "            if stack:\n",
    "                res[i][0] = stack[-1]\n",
    "            stack.append(i)\n",
    "        return [j - i - 1 for i, j in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        sl = SortedList([-1, len(nums)])\n",
    "        ans = [0] * len(nums)\n",
    "        for x, i in sorted([(-x, i) for i, x in enumerate(nums)]):\n",
    "            p = sl.bisect_left(i)\n",
    "            ans[i] = sl[p]-sl[p-1]-1\n",
    "            sl.add(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        has, stark = [[-1, len(nums)] for _ in range(len(nums))], []\n",
    "        for i, v in enumerate(nums):\n",
    "            while stark and nums[stark[-1]] < v: has[stark.pop()][1] = i\n",
    "            if stark: has[i][0] = stark[-1]\n",
    "            stark.append(i)\n",
    "        return [j - i - 1 for i, j in has]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        res, stack = [[-1, len(nums)] for _ in range(len(nums))], []\n",
    "        for i, v in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] < v:\n",
    "                res[stack.pop()][1] = i\n",
    "\n",
    "            if stack:\n",
    "                res[i][0] = stack[-1]\n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        return [j - i - 1 for i, j in res]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        has, stark = [[-1, len(nums)] for _ in range(len(nums))], []\n",
    "        for i, v in enumerate(nums):\n",
    "            while stark and nums[stark[-1]] < v:\n",
    "                has[stark.pop()][1] = i\n",
    "\n",
    "            if stark:\n",
    "                has[i][0] = stark[-1]\n",
    "\n",
    "            stark.append(i)\n",
    "\n",
    "        return [j - i - 1 for i, j in has]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        stack = [0]\n",
    "        right_dict = {}\n",
    "        for i in range(1, len(nums)):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                right_dict[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        for i in stack:\n",
    "            right_dict[i] = len(nums)\n",
    "        stack = [len(nums) - 1]\n",
    "        left_dict = {}\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                left_dict[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        for i in stack:\n",
    "            left_dict[i] = -1\n",
    "        return [right_dict[i] - left_dict[i] - 1 for i in range(len(nums))]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        [1,5,4,3,6]\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1, m2 = {}, {}\n",
    "        st = []\n",
    "        for k, v in enumerate(nums):\n",
    "            if k == 0:\n",
    "                st.append((v, k))\n",
    "            else:\n",
    "                while len(st) > 0 and st[-1][0] < v:\n",
    "                    cur = st.pop()\n",
    "                    m1[cur[1]] = k - 1\n",
    "                st.append((v, k))\n",
    "        if len(st) > 0:\n",
    "            for i in st:\n",
    "                m1[i[1]] = len(nums) - 1\n",
    "        st = []\n",
    "        for i in range(len(nums)):\n",
    "            idx1 = len(nums) - 1 - i\n",
    "            if idx1 == len(nums) - 1:\n",
    "                st.append((nums[idx1], idx1))\n",
    "            else:\n",
    "                while len(st) > 0 and st[-1][0] < nums[idx1]:\n",
    "                    cur = st.pop()\n",
    "                    m2[cur[1]] = idx1 + 1\n",
    "                st.append((nums[idx1], idx1))\n",
    "        if len(st) > 0:\n",
    "            for i in st:\n",
    "                m2[i[1]] = 0\n",
    "\n",
    "\n",
    "        return [m1[i] - m2[i] + 1 for i in range(len(nums))]\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.maximumLengthOfRanges([1,5,4,3,6]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        [1,5,4,3,6]\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1, m2 = {}, {}\n",
    "        st = []\n",
    "        for k, v in enumerate(nums):\n",
    "            if k == 0:\n",
    "                st.append((v, k))\n",
    "            else:\n",
    "                while len(st) > 0 and st[-1][0] < v:\n",
    "                    cur = st.pop()\n",
    "                    m1[cur[1]] = k - 1\n",
    "                st.append((v, k))\n",
    "        if len(st) > 0:\n",
    "            for i in st:\n",
    "                m1[i[1]] = len(nums) - 1\n",
    "        st = []\n",
    "        for i in range(len(nums)):\n",
    "            idx1 = len(nums) - 1 - i\n",
    "            if idx1 == len(nums) - 1:\n",
    "                st.append((nums[idx1], idx1))\n",
    "            else:\n",
    "                while len(st) > 0 and st[-1][0] < nums[idx1]:\n",
    "                    cur = st.pop()\n",
    "                    m2[cur[1]] = idx1 + 1\n",
    "                st.append((nums[idx1], idx1))\n",
    "        if len(st) > 0:\n",
    "            for i in st:\n",
    "                m2[i[1]] = 0\n",
    "        return [m1[i] - m2[i] + 1 for i in range(len(nums))]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
